1. Field
Aspects of embodiments of the present invention are directed toward a sliding window list decoder for error correcting codes.
2. Description of Related Art
Communication and storage technologies are rapidly evolving. 400 Gbit (gigabit) communication systems are in design, while 100 Tbit (terabit) systems are predicted by 2020. Given this growth, error correction power needs to scale up with transmission speed. As transmission rates increase, burst error lengths increase proportionally. For example, the same single bit error event at 10 Mbit (megabit) can affect 1000 bits at 10 Gbit. Traditional serial error correcting code (ECC) decoders (circa 1960) scale badly, and are guaranteed to silently corrupt data for some large errors. For the most part, they are all based on the same mathematics: derive key equation, solve the equation, then recover the correct data. Their latency increases with the correction power (e.g., number of symbols or entries, where each symbol or entry is some quantity of data, such as a byte), and their likelihood to silently corrupt data increases with error size.
Reed-Solomon error correction and other applications of ECC (such as data verification, encryption, and compression) are described in the Reference Application. Example solutions of Reed-Solomon error correction (such as the Welch-Berlekamp algorithm, or just Berlekamp) are described in Mann, The Original View of Reed-Solomon Coding and the Welch-Berlekamp Decoding Algorithm, Ph.D. dissertation, Univ. of Arizona, 2013, the entire content of which is incorporated by reference. Maximum likelihood decoding of Reed-Solomon codes is an NP-hard problem. In particular, there is no known algorithm to choose the most likely decoding for K data symbols and T check (or parity) symbols (i.e., for codewords of N=K+T symbols) having up to T−1 errors by any algorithm in polynomial time with respect to N.
Put another way, the processing complexity of any such known algorithm grows at least exponentially with N. The majority of existing Reed-Solomon error correction techniques, such as Welch-Berlekamp, are serial in nature, and require multiple clock cycles (the clock cycle count being proportional to N) to perform their correction. For more than T/2 errors, decoders such as Welch-Berlekamp have a design flaw such that cases with more than T/2 errors but fewer than T errors can be mistaken for cases with fewer than T/2, resulting in silent data corruption.